package 动态规划;

public class JZ14剪绳子I {

    /**
     * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），
     * 每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？
     * 例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
     *
     * 示例 1：
     * 输入: 2
     * 输出: 1
     * 解释: 2 = 1 + 1, 1 × 1 = 1
     * 示例 2:
     * 输入: 10
     * 输出: 36
     * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
     * 提示：
     * 2 <= n <= 58
     */

    /**
     * 假设 n=10;
     * 长度为1的绳子,最长的长度乘积
     * f(0)=0;
     * f(1)=f(0)*1;
     * f(2)={f(0)*2,f(1)*1,f(2)*0};
     * f(3)={f(1)*2,f(2)*1};
     * f(4)={...};
     */
    public int cuttingRope(int n) {

        if(n<=3){
            return n-1;
        }

        int[] dp=new int[n+1];
        dp[2]=1;
        dp[3]=2;

        for (int i = 4; i <= n; i++) {
            dp[i]=dp[i-1];
            for (int j = i-1; j >= 2; j--) {
                dp[i]=Math.max(dp[i],Math.max(dp[j]*(i-j),j*(i-j)));
            }
        }

        return dp[n];
    }

    //贪心:数字未3时,进行乘才会最大
    public int method2(int n) {
        if (n < 4) {
            return n-1;
        }
        int result=1;
        while (n>4){
            result=result*3;
            n-=3;
        }
        return result*n;
    }

    public int cuttingRope2(int n) {

        if (n < 4) {
            return n-1;
        }
        long result=1;//精髓是long类型
        while (n>4){
            result=(result*3)%1000000007;
            n-=3;
        }
        return (int)result*n%1000000007;
    }

    public static void main(String[] args) {
        JZ14剪绳子I jz=new JZ14剪绳子I();
        int result = jz.cuttingRope2(10);
        System.out.println(result);
        System.out.println(jz.method2(10));
    }

}
